|
The reconstruction conjecture of Stanislaw Ulam is one of the best-known open problems in graph theory. Using the terminology of Frank Harary〔.〕 it can be stated as follows: If ''G'' and ''H'' are two graphs on at least three vertices and ƒ is a bijection from ''V''(''G'') to ''V''(''H'') such that ''G''\ and ''H''\ are isomorphic for all vertices ''v'' in ''V''(''G''), then ''G'' and ''H'' are isomorphic. In 1964 Harary extended the reconstruction conjecture to directed graphs on at least five vertices as the so-called digraph reconstruction conjecture. Many results supporting the digraph reconstruction conjecture appeared between 1964 and 1976. However, this conjecture was proved to be false when P. K. Stockmeyer discovered several infinite families of counterexample pairs of digraphs (including tournaments) of arbitrarily large order.〔. Erratum, ''J. Graph Th.'' 62 (2): 199–200, 2009, , .〕〔.〕〔.〕 The falsity of the digraph reconstruction conjecture caused doubt about the reconstruction conjecture itself. Stockmeyer even observed that “perhaps the considerable effort being spent in attempts to prove the (reconstruction) conjecture should be balanced by more serious attempts to construct counterexamples.”〔 In 1979, Ramachandran revived the digraph reconstruction conjecture in a slightly weaker form called the new digraph reconstruction conjecture. In a digraph, the number of arcs incident from (respectively, to) a vertex ''v'' is called the outdegree (indegree) of ''v'' and is denoted by ''od''(''v'') (respectively, ''id''(''v'')). The new digraph conjecture may be stated as follows: ::If ''D'' and ''E'' are any two digraphs and ƒ is a bijection from ''V''(''D'') to ''V''(''E'') such that ''D''\ and ''E''\ are isomorphic and (''od''(''v''),''id''(''v'')) = (''od''(ƒ(''v'')),''id''(ƒ(''v''))) for all ''v'' in ''V''(''D''), then ''D'' and ''E'' are isomorphic.〔.〕〔.〕 The new digraph reconstruction conjecture reduces to the reconstruction conjecture in the undirected case, because if all the vertex-deleted subgraphs of two graphs are isomorphic, then the corresponding vertices must have the same degree. Thus, the new digraph reconstruction conjecture is stronger than the reconstruction conjecture, but weaker than the disproved digraph reconstruction conjecture. Several families of digraphs have been shown to satisfy the new digraph reconstruction conjecture and these include all the digraphs in the known counterexample pairs to the digraph reconstruction conjecture. As of 2014, no counterexample to the new digraph reconstruction conjecture is known. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「New digraph reconstruction conjecture」の詳細全文を読む スポンサード リンク
|